The present invention relates to transmission of data in a network environment. More specifically, the present invention relates to methods and apparatus for efficiently redirecting or distributing network traffic.
Current traffic distribution or load-balancing algorithms are based on metrics such as “round robin” or “weighted round robin”, “least connections”, and “fastest response.” Round robin generally sequentially distributes traffic portions to each available destination site or server. For example, a first traffic portion goes to a first server; a second portion goes to a second server; etc. After a traffic portion goes to the last available server, the next traffic portion is then distributed to the first server. In the weighted round robin approach, each server has an associated weight value that dictates how large a traffic portion is received by such server during its turn. The least connections approach generally distributes traffic to the server that currently has the least number of connections. The fast response approach distributes traffic to the server that responds the quickest to a service request.
Although these techniques are adequate for certain applications, they all require per flow state information to be kept. When the traffic level (e.g., to the switch) is high, the number of simultaneous flows is also high. Accordingly, these techniques may then consume a relatively large amount of resources to keep the per flow state information. For example, a relatively large amount of memory is utilized.
Network caching represents another distribution technique. By altering the operating system code of an existing router or switch, the router or switch is enabled to recognize and redirect data traffic having particular characteristics such as, for example, a particular protocol intended for a specified port (e.g., TCP with port 80), to one or more network caches connected to the router via an interface having sufficient bandwidth. If there are multiple caches connected to the cache-enabled router, the router selects from among the available caches for a particular request based on the destination IP address specified in the packet. An example of such a network caching technique is embodied in the Web Cache Coordination Protocol (WCCP) provided by Cisco Systems, Inc., a specific embodiment of which is described in copending, commonly assigned, U.S. patent application Ser. No. 08/946,867 for METHOD AND APPARATUS FOR FACILITATING NETWORK DATA TRANSMISSIONS filed Oct. 8, 1997, the entirety of which is incorporated herein by reference for all purposes.
Another specific embodiment of a packet redirection protocol which may be used to implement a network redirection technique is described in copending, commonly assigned, U.S. Provisional Patent Application No. 60/168,862 for METHOD AND APPARATUS FOR REDIRECTING NETWORK TRAFFIC filed Dec. 2, 1999, the entirety of which is incorporated herein by reference for all purposes. According to a specific embodiment described in that application, the network caches have the capability of determining that particular redirected packets should be transmitted back to the redirecting router and reinserted into the original traffic flow. This may be done in a manner transparent to the source or destination of the packets. An example of a case in which packets would need to be reinserted in the original flow might be where the cache recognizes the source and destination pairs identified by the packets as corresponding to a connection requiring IP-based authentication. Another example would be where the cache is overloaded and is currently unable to handle all of the redirected traffic.
In the above described WCCP techniques, a cache system to which a particular packet is redirected is selected based on the contents of the particular packet. The four bytes of the destination address of the particular packet are XOR'ed together. The XOR result is then used as an index to a redirection table. In other words, the index is compared to a plurality of index values within the redirection table. When a matching index is found, the matching index corresponds to a particular cache system. The packet is then redirected to the corresponding cache system.
Although this cache system selection technique works well in certain applications, it is too slow in other applications that require relatively fast redirection since the technique is currently implemented in software. That is, the XOR'ing and matching procedures take a relatively high number of clock cycles to complete. Additionally, it is not practical to implement the cache system selection techniques within hardware (e.g., within an ASIC) since the design time for an ASIC typically takes about 18 months. Each change to the cache selection or distribution algorithms would then require a new ASIC design. In sum, a hardware implementation for the cache system distribution techniques would be too time-consuming and costly.
Therefore, there is a need for more efficient traffic distribution techniques that also provide flexible redesign capabilities.